package com.maltys.dp.backpack;

import java.util.Arrays;
import java.util.List;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/word-break/description/">单词拆分</a>
 */
public class WordBreak {
    public static void main(String[] args) {
        WordBreak targetSum = new WordBreak();
        String[] strings = new String[]{"apple", "pen"};
        List<String> list = Arrays.asList(strings);
        boolean sum = targetSum.wordBreak("applepenapple", list);
        System.out.println(sum);
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[][] dp = new boolean[wordDict.size() + 1][s.length() + 1];
        dp[0][0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k <= i; k++) {
                    String subStr = wordDict.get(k - 1);
                    if (j >= subStr.length()) {
                        String sub = s.substring(j - subStr.length(), j);
                        if (sub.equals(subStr)) {
                            dp[i][j] |= dp[i][j - wordDict.get(k - 1).length()];
                        }
                    }
                }

            }
        }
        return dp[wordDict.size()][s.length()];
    }
}
